// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决

// 例题 1：
// 给你一棵 完整二叉树 的根，这棵树有以下特征：
//
//        叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
//        非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
//        计算 一个节点的值方式如下：
//
//        如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
//        否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
//        返回根节点 root 的布尔运算值。
//
//        完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
//
//        叶子节点 是没有孩子的节点。
//
//
//
//        示例 1：
//
//
//
//        输入：root = [2,1,3,null,null,0,1]
//        输出：true
//        解释：上图展示了计算过程。
//        AND 与运算节点的值为 False AND True = False 。
//        OR 运算节点的值为 True OR False = True 。
//        根节点的值为 True ，所以我们返回 true 。
//        示例 2：
//
//        输入：root = [0]
//        输出：false
//        解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
//
//
//        提示：
//
//        树中节点数目在 [1, 1000] 之间。
//        0 <= Node.val <= 3
//        每个节点的孩子数为 0 或 2 。
//        叶子节点的值为 0 或 1 。
//        非叶子节点的值为 2 或 3 。

// 解题思路：
// 简单的后序遍历
// 每个节点都需要判断左子树和左右子树是 true 或者 false （这就是重复子问题）
// 再根据根节点的运算符号判断是当前树的结果

public class EvaluateTree {
    public boolean evaluateTree(TreeNode root) {
        if(root.val == 0) return false;
        if(root.val == 1) return true;
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? (left || right) : (left && right);
    }
}
